/*
 * @lc app=leetcode.cn id=153 lang=cpp
 *
 * [153] 寻找旋转排序数组中的最小值
 */

// @lc code=start
class Solution
{
 public:
  // 二分的方法
  int findMin(vector<int>& nums)
  {
    int l = 0, r = nums.size() - 1;
    while (l < r)
    {
      int mid = l + r >> 1;
      if (nums[mid] <= nums.back())
        r = mid;
      else
        l = mid + 1;
    }

    return nums[r];
  }

  int findMin(vector<int>& nums)
  {
    /*
    // 判断输入是否合法
    if (nums == null || nums.size() == 0)
    {
        throw new RuntimeException("Invalid inout");
    }*/
    if (nums.size() == 0)
    {
      return 0;
    }

    // 开始处理第一个位置
    int index1 = 0;
    int index2 = nums.size() - 1;
    // 把indexMid初始化为index1的原因：
    // 一旦发现数组中第一个数字小于最后一个数字，表明该数组是排序的
    // 就可以直接返回第一个数字了
    int indexMid = index1;

    // 确保index1在前一个排好序的部分，index2在排好序的后一个部分
    while (nums[index1] >= nums[index2])
    {
      // 如果index1和index2指向相邻的两个数，
      // 则index1指向第一个递增子数组的最后一个数字，
      // index2指向第二个子数组的第一个数字，也就是数组中的最小数字
      if (index2 - index1 == 1)  // 这也是正常情况下循环中止的条件
      {
        indexMid = index2;
        break;
      }

      indexMid = index1 + (index2 - index1) / 2;

      // 特殊情况：如果下标为index1、index2和indexMid指向的三个数字相等，则只能顺序查找
      if (nums[index1] == nums[indexMid] && nums[indexMid] == nums[index2])
      {
        return minNumber(nums, index1, index2);
      }

      // 缩小查找范围
      if (nums[indexMid] >= nums[index1])  // Mid在第一个递增数组
      {
        index1 = indexMid;  // 第一个指针指向Mid
      }
      else if (nums[indexMid] <= nums[index2])  // Mid在第二个递增数组
      {
        index2 = indexMid;
      }
    }
    return nums[indexMid];
  }

  int minNumber(int[] nums, int index1, int index2)
  {
    int result = nums[index1];
    for (size_t i = index1 + 1; i < index2; i++)
    {
      if (result > nums[i])
      {
        result = nums[i];
      }
    }
    return result;
  }

  int findMin(vector<int>& nums)
  {
    int l = 0, r = nums.size() - 1;
    while (l < r)
    {
      int mid = (r - l) / 2 + l;  // 向上取整 取mid
      if (nums[mid] <
          nums[r])  // 这个地方是重点，满足这个条件，说明mid在第二个增数组，此时最小数在mid前面，所以切掉右区间
        r = mid;
      else  // nums[mid] >=
            // nums[r]的情况，此时mid在第一个增数组，最小数在第二个增数组，在mid前面，此时砍掉左区间
        l = mid + 1;
    }
    return nums[l];
  }
};
// @lc code=end
